struct PairingHeap
{
    da node[maxm];
    int l[maxm],r[maxm],root,cnt,size;
    void push(da d)
    {
        size++;
        node[++cnt]=d;
        root=Merge(root,cnt);
    }
    int Merge(int a,int b)
    {
        if(a==0)return b;
        if(b==0)return a;
        if(node[a] > node[b])
            swap(a,b);
        r[b]=l[a];
        l[a]=b;
        return a;
    }
    int MergeBrothers(int a)
    {
        if(a==0)return 0;
        if(r[a]==0)return a;
        int ra=r[a],rra=r[ra];
        r[a]=r[ra]=0;
        return Merge(Merge(a,ra),MergeBrothers(rra));
    }
    da top()
    {
        return node[root];
    }
    void pop()
    {
        size--;
        root=MergeBrothers(l[root]);
    }
    bool empty()
    {
        return size==0;
    }
};
PairingHeap<int> ph;
